class Solution {
public:
    //https://leetcode.cn/problems/sort-an-array/
    vector<int> sortArray(vector<int>& nums) 
    {
        Sort(nums, 0, nums.size() - 1);
        return nums;
    }

    void Sort(vector<int>& nums, int left, int right)//三路快排
    {
        if(right <= left) return;
        int ran = rand();
        int key = ran % (right - left + 1) + left;
        swap(nums[left], nums[key]);
        key = nums[left];
        int l = left - 1, r = (right + 1), i = left;
        for(; i < r; )
        {
            if(nums[i] < key) swap(nums[++l], nums[i++]);
            else if(nums[i] == key) i++;
            else if(nums[i] > key) swap(nums[--r], nums[i]);
        }
        Sort(nums, left, l);
        Sort(nums, r, right);
    }


    //https://leetcode.cn/problems/kth-largest-element-in-an-array/
    int findKthLargest(vector<int>& nums, int k) //O(n)
    {
        srand(time(nullptr));
        int n = 0;
        int left = 0, right = nums.size() - 1;
        return qSort(nums, left, right, k);
    }
    
    int qSort(vector<int>& nums, int left, int right, int k)
    {
        if(right == left) 
        {
            return nums[left];
        }
        int ran = rand();
        int key = nums[ran % (right - left + 1) + left];
        int l = left - 1, r = (right + 1), i = left;
        for(; i < r; )
        {
            if(nums[i] < key) swap(nums[++l], nums[i++]);
            else if(nums[i] == key) i++;
            else if(nums[i] > key) swap(nums[--r], nums[i]);
        }
        int c = right - r + 1, b = r - l - 1;
        if(k <= c) return Sort(nums, r, right, k);
        else if(k <= b+c) return key; 
        else return Sort(nums, left, l, k - b - c);
    }

    //https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
    vector<int> inventoryManagement(vector<int>& stock, int cnt) //思想与上一题一致
    {
        Ssort(stock, 0, stock.size() - 1, cnt);
        return vector<int> (stock.begin(), stock.begin() + cnt);
    }

    void Ssort(vector<int>& nums, int left, int right, int k)
    {
        if(right <= left) return;
        int ran = rand();
        int key = nums[ran % (right - left + 1) + left];
        int l = left - 1, r = (right + 1), i = left;
        for(; i < r; )
        {
            if(nums[i] < key) swap(nums[++l], nums[i++]);
            else if(nums[i] == key) i++;
            else if(nums[i] > key) swap(nums[--r], nums[i]);
        }
        int c = l - left + 1, b = r - l - 1;
        if(k <= b + c) Sort(nums, left, l, k);
        else Sort(nums, r, right, k - b - c);
    }
};